package dynamicProgramming.SingleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/19 10:15
 **/

/**
 * 题目 ：环形房屋盗窃
 * 题目详述 ：
 * 一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。
 * 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
 * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * 给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 *
 * 提示：
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 1000
 */
public class Rob {
    /**
     * 思路 ：
     * 即，由于环形房屋与并列房屋的区别，在于环形房屋需要考虑第0个房屋和第n-1个房屋也是不能够相邻的;
     * （即，小偷是不能够同时进行入第0个房屋和第n-1个房屋进行偷窃的）
     *
     * 核心思想 ：就是将大问题拆分成小问题
     * 即，拆分成（1）第0个房屋到第n-2个房屋所能够偷窃的最大值（2）第1个房屋到第n-1个房屋所能够偷窃的最大值;
     * ===> 问题的解决：max（子问题1结果 ，子问题2结果）;
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int length = nums.length;
        if (length < 2){
            // 由于length >= 1，即此处的length只能够取值为1;
            return nums[0];
        }
        int result1 = iteration(nums , 0 , length - 2);
        int result2 = iteration(nums , 1 , length - 1);
        return Math.max(result1 , result2);
    }
    // 特殊情况 ：即length == 2时，
    private int iteration(int[] nums, int start, int end) {
        int[] redis = new int[2];
        // 即，使用redis[0]来存储nums[0];
        redis[0] = nums[start];
        if(end > start){ // 当end == start时，代表此子数组中有且仅有一个元素;
            // 即，使用redis[1]来存储nums[1];
            // 即，当子数组中有且仅存在两个元素时，需要对于两个元素进行比较，同时获取两个元素中的最大值
            redis[1] = Math.max(nums[start] , nums[start + 1]);
        }
        // 迭代获取从下标start到下标end的房屋所能够偷窃的最大值
        for(int i = start + 2 ; i <= end ; i++){
            // 由于redis[start]和redis[start + 1]都已经被赋予初始值;
            // ===> 所以只需要从start + 2开始，给redis数组进行赋值即可;

            // 为保证redis[0]中所存储的是 下标为start + 2n的redis元素;
            int j = i - start;
            redis[j % 2] = Math.max(redis[(j - 1) % 2] , redis[(j - 2) % 2] + nums[i]);
        }
        // 所需要返回的是，redis数组中最后存储的元素（即，代表了从第start间房屋到第end间房屋所能够偷窃到的最大财物）
        return redis[((end - start) % 2)];
    }
}
